package cn.suchan.jianzhi.q29_array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeSet;

/**
 * 知识点：最小的K个数
 * 题目描述
 * 输入n个整数，找出其中最小的K个数。
 * 例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
 *
 * @author
 * @date 2019/05/30
 */
public class Solution {

    /**
     * 借助TreeSet的特点，把重复的元素去掉，并直接排序（刚学到的，现学现用，哈哈哈）
     *
     * @param input
     * @param k
     * @return
     */
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList resultList = new ArrayList();
        if (input.length <= 0 || input == null || k > input.length) {
            return resultList;
        }
        // 借助TreeSet的特点，把重复的元素去掉，并直接排序
        TreeSet<Integer> treeSet = new TreeSet();
        for (int i = 0; i < input.length; i++) {
            treeSet.add(input[i]);
        }

        resultList.addAll(treeSet);
        // 应该移除的元素计数
        int rm = resultList.size() - k;
        while (rm > 0) {
            // 因为是排好序了的，所以直接移除最后面的就好了
            resultList.remove(resultList.size() - 1);
            rm--;
        }
        return resultList;
    }

    /**
     * 也可以直接对数组进行排序，但是这里我没有去重
     *
     * @param input
     * @param k
     * @return
     */
    public ArrayList<Integer> GetLeastNumbers_Solution1(int[] input, int k) {
        ArrayList resultList = new ArrayList();
        if (input.length <= 0 || input == null || k > input.length) {
            return resultList;
        }
        // 对数组进行排序
        for (int i = 0; i < input.length - 1; i++) {
            for (int j = i + 1; j < input.length; j++) {
                if (input[i] > input[j]) {
                    int temp = input[i];
                    input[i] = input[j];
                    input[j] = temp;
                }
            }
        }

        for (int i = 0; i < k; i++) {
            resultList.add(input[i]);
        }
        return resultList;
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 1, 3, 3, 8, 9, 5, 6};
        Solution solution = new Solution();
        ArrayList<Integer> result = solution.GetLeastNumbers_Solution1(arr, 5);
        System.out.println(result);
    }
}
